Today, a storage device including a nonvolatile memory is widely used. As one of the nonvolatile memory, a NAND-type solid state drive (SSD) is known. SSDs are used as main storages of various computing devices because of low power consumption and high-speed performance. For such memory systems, an encoding technology of encoding data to be written using data patterns is developed to reduce exhaustion of memory cells.
However, according to the encoding technology, it would be necessary to attach information indicating content of the encoding as supplementary information to each user data. As the amount of the supplementary information increases, the amount of user data that can be written on each page of a nonvolatile memory decreases.